The Twofish Encryption Algorithm: A 128-Bit Block Cipher The Twofish Encryption Algorithm: A 128-Bit Block Cipher
by Bruce Schneier ; John Kelsey ; Doug Whiting ; David Wagner ; Chris Hall ; Niels Ferguson
Wiley Computer Publishing, John Wiley & Sons, Inc.
ISBN: 0471353817   Pub Date: 03/01/99
  

Previous Table of Contents Next


However, it is dangerous to rely solely on theory when designing ciphers. Ciphers provably secure against differential cryptanalysis have been attacked with higher-order differentials [Lai94, Knu95b] or the interpolation attack [JK97]: KN-cipher [NK95] was attacked in [JK97, SMK98], Kiefer [Kie96] in [JK97], and a version of CAST in [MSK98a]. The CAST cipher cryptanalyzed in [MSK98a] is not CAST-128, but it does illustrate that while the CAST design procedure [AT93, HT94a] can create ciphers resistant to differential and linear cryptanalysis, it does not create ciphers resistant to whatever form of cryptanalysis comes next. SNAKE [LC97], another cipher provably secure against differential and linear cryptanalysis, was successfully broken using the interpolation attack [MSK98b). When designing a cipher, it is prudent to assume that new attacks will be developed in order to break it.

We took a slightly different approach in our design. Instead of trying to optimize Twofish against known attacks, we tried to make Twofish strong against both known and unknown attacks. While it is impossible to optimize a cipher design for resisting attacks that axe unknown, conservative design and overengineering can instill some confidence.

Many elements of Twofish reflect this philosophy. We used well-studied design elements throughout the algorithm. We started with a Feistel network, probably the most studied block-cipher structure, instead of something newer like an unbalanced Feistel network [SK96, ZMI90] or a generalized Feistel network [Nyb96].

We did not implement multiplication mod 216 + 1 (as in IDEA or MMB [DGV93]) or data-dependent rotations (as in Madryga [Mad84] and RC54 or Akelarre [AGMP96]5) for non-linearity. The most novel design elements we used-MDS matrices and PHTs-are only intended for diffusion (and are used in Square [DKR97] and SAFER, respectively).


4RC5’s security is almost wholly based on data-dependent rotations. Although initial cryptanalysis was promising [KY95] (see also [Se198]), subsequent research [KM97, BK98] suggests that there is considerably more to learn about the security properties of data-dependent rotations.
5Akelaxre was severely broken in [FS97, KR97].

We used key-dependent S-boxes because they offer adequate protection against known statistical attacks and are likely to offer protection to any unknown similar attacks. We defined Twofish at 16 rounds, even though our analysis cannot break anywhere near that number. We added one-bit rotations to prevent potential attacks that relied solely on the byte structure. We designed a very thorough key schedule to prevent related-key and weak-key attacks.

6.3 Simple Design

A guiding design principle behind Twofish is that the round function should be simple enough for us to keep in our heads. Anecdotal evidence from algorithms like FEAL [SM88], CAST, and Blowfish indicates that complicated round functions are not always better than simple ones. Also, complicated round functions are harder to analyze and rely on more ad hoc arguments for security (e.g., REDOC-II [CW91]).

However, with enough rounds, even bad round functions can be made to be secure.6 Even a simple round function like TEA’s [WN95] or RC5’s seems secure after 32 rounds [BK98]. In Twofish, we tried to create a simple round function and then iterate it more than enough times for security.


6Student cryptography projects bear this observation out. At 16 rounds, the typical student cipher fares rather badly against a standard suite of statistical tests. At 32 rounds, it looks better. At 128 rounds, even the worst designs look very good.

6.3.1 Reusing Primitives

One of the ways to simplify a design is to reuse the same primitives in multiple parts of a cipher. Cryptographic design does not lend itself to the adage of not putting all your eggs in one basket. Since any particular “basket” has the potential of breaking the entire cipher, it makes more sense to use as few baskets as possible—and to scrutinize those baskets intensely.

To that end, we used essentially the same construction (8-by-8-bit key-dependent S-boxes consisting of alternating fixed permutations and subkey XORs followed by an MDS matrix followed by a PHT) in both the key schedule and the round function. The differences were in the key material used (the round function’s g function uses a list of key-derived words processed by an RS code; the key schedule’s h function uses individual key bytes directly) and the rotations. The rotations represent a performance-driven design trade-off: putting the additional rotations into F would have unacceptably slowed down the cipher performance on high-end machines. The use of the RS code to derive the key material for g adds substantial resistance to related-key attacks.

While many algorithms reuse the encryption operation in their key schedule (e.g., Blowfish, Panama [DC98a, DC98b], RC4, CRISP [Lee96], YTH [YTH96]), and several alternative DES key schedules reuse the DES operation [Knu94b, BB96], we are unaware of any that reuse the same primitives in exactly this manner.7 We feel that doing so greatly simplifies the analysis of Twofish, since the same kinds of analysis can apply to the cipher in two different ways.


7The closest idea is an alternate DES key schedule that uses the DES round function, both the 32-bit block input and 48-bit key input, to create round subkeys [Ada97b].

6.3.2 Reversibility

While it is essential that any block cipher be reversible, so that ciphertext can be decrypted back into plaintext, it is not necessary that the identical function be used for encryption and decryption. Some block ciphers are reversible with changes only in the key schedule (e.g., DES, IDEA, Blowfish), while others require different algorithms for encryption and decryption (e.g., SAFER, Serpent, Square).

The Twofish encryption and decryption round functions are slightly different, but are built from the same blocks. That is, it is simple to build a hardware or software module that does both encryption and decryption without duplicating much functionality, but the exact same module cannot both encrypt and decrypt.

Note that having the cipher work essentially the same way in both directions is a nice feature in terms of analysis, since it lets analysts consider chosen-plaintext and chosen-ciphertext attacks at once, rather than considering them as separate attacks with potentially radically different levels of difficulty [Cop98].


Previous Table of Contents Next